class Solution(object):
    def shortestPathBinaryMatrix(self, grid):
        m = len(grid)
        n = len(grid[0])
        if grid[0][0] or grid[m - 1][n - 1]:
            return -1
        now = {(0, 0)}
        grid[0][0] = 1
        dist = 1
        while now:
            next_set = set()
            for x, y in now:
                if x == m - 1 and y == n - 1:
                    return dist
                else:
                    for ux, uy in [(x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y - 1),
                                   (x + 1, y), (x + 1, y + 1)]:
                        if 0 <= ux < m and 0 <= uy < n:
                            if not grid[ux][uy]:
                                next_set.add((ux, uy))
                                grid[ux][uy] = 1
            now = next_set
            dist += 1
        return -1